package com.mystudy.leetcode.problem.tree.p_107;

import com.mystudy.leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: infoalgorithm
 * @description: 二叉树的层次遍历||
 * @author: zhouzhilong
 * @create: 2019-07-24 14:07
 **/
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //先找到深度，然后递减即可
        int depth = maxDepth(root);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < depth; i++) {
            result.add(new ArrayList<>());
        }
        levelOrderBottom(root, depth, result);
        return result;
    }

    private int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftDepth = maxDepth(node.left);
        int rightDepth = maxDepth(node.right);

        return leftDepth >= rightDepth ? leftDepth + 1 : rightDepth + 1;


    }


    private void levelOrderBottom(TreeNode node, int depth, List<List<Integer>> list) {
        if(node == null){
            return;
        }
        list.get(depth-1).add(node.val);

        levelOrderBottom(node.left,depth-1,list);
        levelOrderBottom(node.right,depth-1,list);
    }


}
